package dynamicprogramming;

import java.util.LinkedList;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/4 1:04
 * https://leetcode-cn.com/problems/target-sum/
 */
public class FindTargetSumWays {

    private static int count;
    static LinkedList<Character> list;

    /**
     * 回溯法(超出时间限制）
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays(int[] nums, int target) {
        list = new LinkedList<>();
        count = 0;
        char[] c = {'+', '-'};
        backTracking(nums, target, c);
        return count;
    }

    private static void backTracking(int[] nums, int target, char[] c) {
        if (list.size() == nums.length) {
            //验证和是否等于target
            int sum = list.getFirst().equals('+') ? nums[0] : -nums[0];
            for (int i = 1; i < nums.length; i++) {
                Character poll = list.get(i);
                if (poll.equals('-')) {
                    sum -= nums[i];
                } else {
                    sum += nums[i];
                }
            }
            if (sum == target) {
                count++;
            }
            return;
        }
        for (int i = 0; i < c.length; i++) {
            list.offer(c[i]);
            backTracking(nums, target, c);
            list.removeLast();
        }
    }

    /**
     * 转化为01背包问题，数的前面是加法的和 x  数的前面是减法的和 sum -x     x - (sum - x) = target  x = (target+sum)/2
     * dp[j]表示装满容量为j的背包有几种方法
     * 递推公式：dp[j] += dp[j-nums[i]]
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWays1(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        int x = (target + sum) / 2;
        if ((target + sum) % 2 != 0) {
            return 0;
        }
        target = Math.abs(target);
        if(target > sum){
            return 0;
        }
        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = x; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[x];
    }

    public static void main(String[] args) {
        int[] nums = {1};
        System.out.println(findTargetSumWays1(nums, 1));
//        System.out.println(count);
    }
}
